package com.algorithm.ch1.cjm.string;

/**
 * 请编写一个函数，其功能是将输入的字符串反转过来。
 * <p>
 * 示例：
 * <p>
 * 输入：s = "hello"
 * 返回："olleh"
 */
public class ReverseString {

    // 暴力法
    public String reverseString(String s) {
        char[] chars = s.toCharArray();
        int i = 0;
        for (char c : chars) {
            if (i < chars.length / 2) {
                char temp = chars[i];

                chars[i] = chars[chars.length - 1 - i];

                chars[chars.length - 1 - i] = temp;

                i++;
            } else {
                break;
            }
        }
        s = String.valueOf(chars);
        return s;
    }

    // 借用StringBuilder
    public String reverseString1(String s) {
        StringBuilder builder = new StringBuilder(s);
        builder.reverse();
        return builder.toString();
    }

    // 递归法，动态规划
    public String reverseString2(String s) {
        if (s.length() <= 1) {
            return s;
        }
        String left = s.substring(0, s.length()/2);
        String right = s.substring(s.length()/2);

        return reverseString2(right) + reverseString2(left);
    }

    public static void main(String[] args) {
        String s = "hello";
        ReverseString string = new ReverseString();
        String string1 = string.reverseString1(s);
        String string2 = string.reverseString2(s);
        System.out.println(string1);
        System.out.println(string2);
    }
}
